package com.zdp.algorithm.stackandqueue;

import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;

/**
 * 可见山峰数量
 * @author Zhengdp
 * @date 2023年01月17日 14:40
 */
public class GetVisibleNum {
}

/**
 * 可见山峰数量进阶，数组中有重复元素
 * 主要利用 单调栈（单调递减） ==> 遵循小找大原则，找到小的山峰从两个方向可以看到的大的山峰
 * 单调递减栈可以保证，栈顶元素的下一个元素一定是大于栈顶元素的，那么只需要遍历到大于栈顶元素的山峰，那么双边可见山峰的条件就成立了。
 * left > cur < right ==> cur 可以看到 left 和 right 两座山峰。
 * 其次，如果 cur山峰是一系列相同高度的山峰，那么这几个相同高度的山峰是两两可见的 C(2,k)
 * 也就是说，如果 cur.count > 1 ==> 可见山峰的数量为 ： cur.count * 2 + C(2,cur.count)
 * 当遍历结束时，则需要对栈中的元素进行清算。
 * 清算分为三个阶段：
 * 1. 栈中元素大于等于3个 ==> 此时的处理与之前遍历的处理方式相同
 * 2. 栈中的元素 等于2个 ==> 判断栈的最后一个山峰的数量是否大于1，如果大于1，因为是环状的，还是会形成两队可见山峰
 *                          如果等于1 ==> 只会生成一对可见山峰 （相同高度的山峰还是按C(2,k)来计算）
 * 3. 栈中的元素 只剩一个 ==> 判断是否有相同高度的山峰，如果有 C(2,k),如果没有，返回0
 */
class GetVisibleNumImpl2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()) {
            int n = in.nextInt();
            int[] arr = new int[n];
            for(int i = 0; i < n ; i ++) {
                arr[i] = in.nextInt();
            }
            System.out.println(getVisibleNum(arr));
        }
    }

    private static int getVisibleNum(int[] arr) {
        int result = 0;
        Stack<Record> maxQueue = new Stack<>();
        // 找到最大值
        int max = Integer.MIN_VALUE;
        int maxIndex = 0 ;
        for(int i = 0; i < arr.length;i++) {
            if(max < arr[i]) {
                max = arr[i];
                maxIndex =i;
            }
        }
        int length = arr.length;
        maxQueue.push(Record.buildRecord(1,arr[maxIndex]));
        // 遍历
        for(int i = maxIndex+1 ; (i%length) != maxIndex ; i++ ) {
            int index = i % length;
            Record right = Record.buildRecord(1,arr[index]);
            while(!maxQueue.isEmpty() && maxQueue.peek().value < right.value) {
                result += getNum(maxQueue,right);
            }
            if(maxQueue.isEmpty()){
                maxQueue.push(right);
            }else if(maxQueue.peek().value == right.value) {
                maxQueue.peek().countIncre();
            }else{
                maxQueue.push(right);
            }
        }

        // 清算
        while(!maxQueue.isEmpty()){
            result += getNum(maxQueue,null);
        }
        return result;
    }

    private static int getNum(Stack<Record> stack,Record right) {
        int result = 0;
        Record cur = stack.pop();
        if(right == null) {
            // 最后清算阶段
            if(stack.size()>=2) {
                // 还有至少3个元素
                result = 2*cur.count + getC(cur);
            }else if(stack.isEmpty()) {
                // 最后一个元素
                result = cur.count == 1 ? 0 :getC(cur);
            }else {
                // 最后两个元素
                Record left = stack.peek();
                result = left.count >= 2 ? 2*cur.count + getC(cur) : cur.count + getC(cur);
            }
        }else {
            // 遍历阶段
            result = 2 *cur.count + getC(cur);
        }
        return  result;
    }

    // C(2,k)
    private static int getC(Record record) {
        if(record.count <= 1){
            return 0;
        }
        return record.count * (record.count -1) / 2 ;
    }


}

class Record {
    public int count;
    public int value;

    public static Record buildRecord(int count,int value) {
        Record record =  new Record();
        record.count = count;
        record.value =value;
        return record;
    }

    public void setCount(int count) {
        this.count = count;
    }

    public void countIncre(){
        this.count = this.count + 1;
    }
}

/**
 * 可见山峰数量原题，数组中无重复
 */
class GetVisibleNumImpl1 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        GetVisibleNumImpl1 impl1 = new GetVisibleNumImpl1();
        while(num-->0) {
            int n = in.nextInt();
            int p = in.nextInt();
            int m = in.nextInt();
            System.out.println(impl1.getVisibleNum(n));
        }
    }

    public int getVisibleNum(int num) {
        if(num == 0 || num == 1){
            return 0;
        }
        if(num == 2) {
            return  1;
        }
        return 2 * num - 3;
    }
}
